package src.hash;

import java.util.Arrays;

public class no41 {
    //缺失的第一个正数

    public int firstMissingPositive(int[] nums) {
        //用max+1作为数组大小会超出内存限制，会因为有一个很大的元素就开辟长数组，浪费空间
        int max = Arrays.stream(nums).max().getAsInt();
        int[] hashArray = new int[max + 1];  // arr[0]不存元素
        for (int n : nums) {
            if (n > 0) {
                hashArray[n]++;
            }
        }
        for (int i = 1; i < hashArray.length; i++) {
            if (hashArray[i] == 0) {
                return i;
            }
        }
        return max + 1;

    }

    public int firstMissingPositive2(int[] nums) {
        //可以不用max+1作为hash数组长度，直接用nums.length+1
        //因为缺失的正数一定在[1,n+1]范围内，<0 和 >length的数都不用往数组里映射
        int n = nums.length;
        int[] hashArray = new int[n + 1];
        for (int i : nums) {
            if (i > 0 && i <= n) {
                hashArray[i]++;
            }
        }
        for (int i = 1; i < n + 1; i++) {
            if (hashArray[i] == 0) {
                return i;
            }
        }
        return n + 1;
    }

    //上面方法还是开辟数组了，可以不用开辟数组，直接原地哈希，不映射元素，在原数组上交换元素，1放在0的位置
    public int firstMissingPositive3(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
//            if (nums[i] == i + 1) {
//                continue;
//            }
            while (nums[i] > 0 && nums[i] <= n && nums[i]!=nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }

    private void swap(int[] nums,int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
